#include <bits/stdc++.h>
using namespace std;

/*
407. 接雨水 II
已解答
困难
相关标签
premium lock icon
相关企业
给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。

 

示例 1:



输入: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
输出: 4
解释: 下雨后，雨水将会被上图蓝色的方块中。总的接雨水量为1+2+1=4。
示例 2:



输入: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
输出: 10
 

提示:

m == heightMap.length
n == heightMap[i].length
1 <= m, n <= 200
0 <= heightMap[i][j] <= 2 * 104
 
*/

// 法一 最小堆 维护 最边界递归进去 
class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        // 木桶原理类似 最小的为标准  存水量取决于外围或已处理单元格形成的最低边界
        // 先排序 找最小
        int m = heightMap.size();
        int n = heightMap[0].size();
        // 边界处理一下
        if (m < 3 || n < 3)     return 0;

        // arrived  flag
        vector<vector<bool>>    visited(m, vector<bool>(n, false));
        // 优先队列 最小堆来维护
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;

        // init edge  最外层的不能存水 初始化边界
        // first  last 
        for (int j = 0; j < n; j++) {
            pq.emplace(heightMap[0][j], 0, j);
            pq.emplace(heightMap[m - 1][j], m - 1, j);
            visited[0][j] = true;
            visited[m - 1][j] = true;
        }
        // first col last col  continue 上面的row
        for (int i = 0; i < m - 1; i++) {
            pq.emplace(heightMap[i][0], i, 0);
            pq.emplace(heightMap[i][n - 1], i, n - 1);
            visited[i][0] = true;
            visited[i][n - 1] = true;
        }

        // 4 dir offset
        vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int ans = 0;        // 积水量

        // 从 bottom --> top(max)
        while (!pq.empty()) {
            // cur 单元格
            auto [h, i, j] = pq.top();
            pq.pop();

            // 四个方向的neibor
            for (auto [di, dj] : dirs) {
                int ni = i + di;
                int nj = j + dj;
                // neibor 在 矩阵范围 未被访问
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && !visited[ni][nj]) {
                    // update flag
                    visited[ni][nj] = true;

                    // 邻居存水量 
                    if (heightMap[ni][nj] < h)  ans += h - heightMap[ni][nj];

                    // 迭代递归 neibor 变成 新的edge  积水后水位与边界齐平，若无积水则自身高度为新边界
                    pq.emplace(max(h, heightMap[ni][nj]), ni, nj);
                }
            }
        }
        return ans;
    }
};

// 法二  贪心分解 二维-->一维
typedef pair<int, int> pii;

class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {  
        // 边界情况：行数或列数≤2时，无法形成积水区域（水会从边缘流走）
        if (heightMap.size() <= 2 || heightMap[0].size() <= 2) {
            return 0;
        }  
        
        int m = heightMap.size();
        int n = heightMap[0].size();
        // 最小堆（小顶堆）：存储(高度, 编码坐标)，按高度升序排列（每次取最低边界）
        // 坐标编码：i*n + j（将二维坐标转为一维，简化存储）
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        // 访问标记：避免重复处理同一单元格
        vector<vector<bool>> visit(m, vector<bool>(n, false));
        
        // 初始化：将外围边界（第一行、最后一行、第一列、最后一列）加入堆
        // 外围单元格无法存水，作为初始边界（水会从外围流出）
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                    pq.push({heightMap[i][j], i * n + j});
                    visit[i][j] = true;
                }
            }
        }

        int res = 0; // 总积水量
        // 四个方向偏移量（上、右、下、左）
        int dirs[] = {-1, 0, 1, 0, -1};
        
        // 从最低边界开始扩展，计算积水
        while (!pq.empty()) {
            pii curr = pq.top(); // 取出当前最低的边界单元格
            pq.pop();            
            // 检查四个方向的邻居
            for (int k = 0; k < 4; ++k) {
                // 解码坐标：nx=行，ny=列（通过编码值反推）
                int nx = curr.second / n + dirs[k];
                int ny = curr.second % n + dirs[k + 1];
                // 确保邻居在矩阵范围内且未被访问
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visit[nx][ny]) {
                    // 若邻居高度低于当前边界，可积水（差值为积水量）
                    if (heightMap[nx][ny] < curr.first) {
                        res += curr.first - heightMap[nx][ny]; 
                    }
                    // 标记邻居为已访问，加入堆作为新边界
                    // 新边界高度取max(邻居自身高度, 当前边界高度)（积水后水位与边界齐平）
                    visit[nx][ny] = true;
                    pq.push({max(heightMap[nx][ny], curr.first), nx * n + ny});
                }
            }
        }
        
        return res;
    }
};

// 法三 法一的常数级优化
class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {  
        // 边界过滤：无法形成积水的情况
        if (heightMap.size() <= 2 || heightMap[0].size() <= 2) {
            return 0;
        }  
        
        int m = heightMap.size();
        int n = heightMap[0].size();
        // 最小堆：直接存储(高度, 行, 列)，避免坐标编码/解码
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
        // 用char数组存储访问标记，提升访问速度（比vector<bool>快）
        vector<vector<char>> visited(m, vector<char>(n, 0));
        
        // 初始化外围边界（边缘单元格无法存水，作为初始边界）
        // 第一行和最后一行
        for (int j = 0; j < n; ++j) {
            pq.emplace(heightMap[0][j], 0, j);
            pq.emplace(heightMap[m-1][j], m-1, j);
            visited[0][j] = 1;
            visited[m-1][j] = 1;
        }
        // 第一列和最后一列（跳过已加入的边缘行）
        for (int i = 1; i < m-1; ++i) {
            pq.emplace(heightMap[i][0], i, 0);
            pq.emplace(heightMap[i][n-1], i, n-1);
            visited[i][0] = 1;
            visited[i][n-1] = 1;
        }

        int res = 0;
        // 四向偏移（上、下、左、右），用pair数组直观存储
        const vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        // 从最低边界开始扩展
        while (!pq.empty()) {
            auto [h, i, j] = pq.top();  // 直接获取当前边界的高度和坐标
            pq.pop();
            
            // 遍历四个方向的邻居
            for (const auto& [di, dj] : dirs) {
                int ni = i + di;
                int nj = j + dj;
                // 检查邻居是否在矩阵内且未访问
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && !visited[ni][nj]) {
                    visited[ni][nj] = 1;  // 标记为已访问
                    
                    // 计算当前邻居的积水量（若低于边界）
                    if (heightMap[ni][nj] < h) {
                        res += h - heightMap[ni][nj];
                    }
                    
                    // 新边界高度取max(自身高度, 当前边界高度)，加入堆
                    int new_h = max(h, heightMap[ni][nj]);
                    pq.emplace(new_h, ni, nj);
                }
            }
        }
        
        return res;
    }
};

// 法四 头铁 其实自己写的 不如标准库优先队列
namespace scData {
    // 堆节点：存储(高度, 行坐标, 列坐标)，用于最小堆排序
    struct HeapNode {
        int h, i, j;
        HeapNode(int h_, int i_, int j_) : h(h_), i(i_), j(j_) {}
    };

    // 自定义最小堆：按高度升序排列，用于高效获取当前最低边界
    class MinHeap {
    private:
        HeapNode**data;   // 存储堆元素的数组
        int capacity;     // 堆容量（动态扩容）
        int size;         // 当前元素数量

        // 扩容：当元素满时翻倍容量
        void resize() {
            capacity *= 2;
            HeapNode** newData = new HeapNode*[capacity];
            for (int i = 0; i < size; ++i) newData[i] = data[i];
            delete[] data;
            data = newData;
        }

        // 上浮：将新插入元素调整到正确位置（维护最小堆性质）
        void bubbleUp(int idx) {
            while (idx > 0) {
                int parent = (idx - 1) / 2;
                if (data[idx]->h >= data[parent]->h) break;
                swap(data[idx], data[parent]);
                idx = parent;
            }
        }

        // 下沉：将堆顶元素调整到正确位置（维护最小堆性质）
        void bubbleDown(int idx) {
            while (true) {
                int left = 2 * idx + 1, right = 2 * idx + 2, smallest = idx;
                if (left < size && data[left]->h < data[smallest]->h) smallest = left;
                if (right < size && data[right]->h < data[smallest]->h) smallest = right;
                if (smallest == idx) break;
                swap(data[idx], data[smallest]);
                idx = smallest;
            }
        }

    public:
        MinHeap() : capacity(16), size(0) { data = new HeapNode*[capacity]; }
        
        ~MinHeap() {  // 释放所有节点内存，避免泄漏
            for (int i = 0; i < size; ++i) delete data[i];
            delete[] data;
        }

        MinHeap(const MinHeap&) = delete;  // 禁止拷贝，避免内存问题
        MinHeap& operator=(const MinHeap&) = delete;

        // 插入元素：添加到堆尾并上浮调整
        void push(int h, int i, int j) {
            if (size == capacity) resize();
            data[size] = new HeapNode(h, i, j);
            bubbleUp(size++);
        }

        // 弹出堆顶元素：先通过引用保存值，再释放内存并下沉调整（避免悬垂指针）
        bool pop(HeapNode& out) {
            if (size == 0) return false;
            out.h = data[0]->h;
            out.i = data[0]->i;
            out.j = data[0]->j;
            delete data[0];
            if (--size > 0) {
                data[0] = data[size];
                bubbleDown(0);
            }
            return true;
        }

        bool empty() const { return size == 0; }  // 堆是否为空
    };

    // 自定义二维数组：用一维存储模拟二维，高效存储访问标记（比vector<vector<bool>>快）
    class Array2D {
    private:
        char* data;  // 一维数组存储数据
        int rows, cols;

    public:
        Array2D(int r, int c, char val = 0) : rows(r), cols(c) {
            data = new char[r * c];
            for (int i = 0; i < r * c; ++i) data[i] = val;
        }

        ~Array2D() { delete[] data; }  // 释放内存

        Array2D(const Array2D&) = delete;
        Array2D& operator=(const Array2D&) = delete;

        char& at(int i, int j) { return data[i * cols + j]; }  // 访问(i,j)位置元素
    };
}

class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {  
        // 边界情况：行数或列数≤2时无法积水（水会从边缘流出）
        if (heightMap.size() <= 2 || heightMap[0].size() <= 2) return 0;
        
        int m = heightMap.size(), n = heightMap[0].size();
        scData::MinHeap heap;          // 最小堆：维护当前最低边界
        scData::Array2D visited(m, n); // 访问标记：避免重复处理
        
        // 初始化外围边界（边缘单元格无法存水，作为初始边界）
        for (int j = 0; j < n; ++j) {  // 第一行和最后一行
            heap.push(heightMap[0][j], 0, j);
            visited.at(0, j) = 1;
            heap.push(heightMap[m-1][j], m-1, j);
            visited.at(m-1, j) = 1;
        }
        for (int i = 1; i < m-1; ++i) {  // 第一列和最后一列（跳过首尾行）
            heap.push(heightMap[i][0], i, 0);
            visited.at(i, 0) = 1;
            heap.push(heightMap[i][n-1], i, n-1);
            visited.at(i, n-1) = 1;
        }

        int res = 0;  // 总积水量
        const int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};  // 四向偏移
        scData::HeapNode curr(0, 0, 0);  // 接收弹出的堆顶元素
        
        // 从最低边界开始扩展：每次处理当前最低的边界，计算邻居积水
        while (!heap.empty()) {
            heap.pop(curr);  // 获取当前最低边界
            int h = curr.h, i = curr.i, j = curr.j;
            
            // 检查四向邻居
            for (const auto& dir : dirs) {
                int ni = i + dir[0], nj = j + dir[1];
                // 邻居在范围内且未访问
                if (ni >= 0 && ni < m && nj >=0 && nj < n && !visited.at(ni, nj)) {
                    visited.at(ni, nj) = 1;
                    // 若邻居低于当前边界，差值为积水量
                    if (heightMap[ni][nj] < h) res += h - heightMap[ni][nj];
                    // 邻居成为新边界（高度取max(自身, 当前边界)）
                    heap.push(max(h, heightMap[ni][nj]), ni, nj);
                }
            }
        }
        
        return res;
    }
};